#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
struct Node{
Node *left, *right, *p, *child;
int key, degree;
bool mark;
Node(int _key, bool _mark=false): key(_key), mark(_mark){
left=this; right=this;
p=nullptr; child=nullptr;
degree=0;
}
};
struct FibHeap{
Node* min;
int n;
FibHeap(void){
min=nullptr;
n=0;
}
~FibHeap(){}
int maxDegree(void){
int D=static_cast<int>(log(this->n)/log(2));
return D;
}
void Insert(int key){
Node* x=new Node(key);
if(this->min==nullptr) this->min=x;
else if(this->n==1){
this->min->left=x;
this->min->right=x;
x->left=this->min;
x->right=this->min;
if(x->key<this->min->key) this->min=x;
} else {
Node* oriRight=this->min->right;
oriRight->left=x;
this->min->right=x;
x->left=this->min;
x->right=oriRight;
if(x->key<this->min->key) this->min=x;
}
this->n++;
}
void InsertRoot(Node* x){
Node* origLeft=this->min->left;
this->min->left=x;
x->left=origLeft;
x->right=this->min;
if(this->min->key>x->key) this->min=x;
}
int Minimum(void){
if(this->min==nullptr) return 0;
return this->min->key;
}
void Union(FibHeap* other){
Node* Left=other->min;
Node* Right=other->min->right;
while(Right!=Left){
Right=Right->right;
}
Right=Right->left;
Node* origLeft=this->min->left;
origLeft->right=Left;
Left->left=origLeft;
this->min->left=Right;
Right->right=this->min;
if(this->min->key>other->min->key) this->min=other->min;
this->n+=other->n;
delete other;
}
void Link(Node* y, Node* x){
Node* yLeft=y->left;
Node* yRight=y->right;
y->left->right=yRight;
y->right->left=yLeft;
x->degree++;
if(x->child==nullptr) x->child=y;
else {
Node* origxcr=x->child->right;
y->right=origxcr;
y->left=x->child;
x->child->right=y;
origxcr->left=y;
}
}
void Consolidate(void){
int D=maxDegree();
Node** A=new Node*[D+1];
for(int i=0; i<D; ++i) A[i]=nullptr;
Node* w=this->min;
Node* origw=w;
do{
Node* x=w;
int d=x->degree;
while(A[d]!=nullptr){
Node* y=A[d];
if(x->key>y->key){
Node* tmp=x;
x=y;
y=tmp;
}
Link(y, x);
A[d]=nullptr;
d++;
}
A[d]=x;
w=w->right;
}while(w!=origw);
this->min=nullptr;
for(int i=0; i<=D; ++i){
if(A[i]!=nullptr){
if(this->min==nullptr) this->min=A[i];
else {
if(this->min->key>A[i]->key) this->min=A[i];
}
}
}
delete[] A;
}
void ExtractMin(void){
Node* z=this->min;
if(z!=nullptr){
Node* x=z->child;
if(x!=nullptr){
Node* origx=x;
do{
InsertRoot(x);
x->p=nullptr;
x=x->right;
} while(x!=origx);
}
Node* Left=z->left;
Node* Right=z->right;
Left->right=Right;
Right->left=Left;
if(z==z->right){
this->min=nullptr;
} else {
this->min=z->right;
Consolidate();
}
this->n--;
delete z;
}
}
};
int main(void){
int sz=10;
FibHeap* tree1=new FibHeap();
int* list=new int[sz];
for(int i=0; i<sz; i++){
int rdn=591*i%17+1;
tree1->Insert(rdn);
list[i]=rdn;
if(i%7==6){
tree1->ExtractMin();
std::cout<<"Extract at: "<<rdn<<'['<<i<<']'<<std::endl;
}
std::cout<<tree1->min->key<<std::endl;
}
for(int i=0; i<sz; ++i) std::cout<<list[i]<<' ';
std::cout<<std::endl;
std::cout<<tree1->Minimum()<<std::endl;
return 0;
}